In data packet based communication systems, i.e. in which information to be transmitted is divided into a plurality of packets and the individual packets are sent over a communication network, it is known to provide queue buffers at various points in the network. A buffer may be a sending or input buffer (i.e. a buffer for data packets that are to be sent over a link) or a receiving or output buffer (i.e. a buffer for data packets that have already been sent over a link).
Packets for transporting data may also be called by any of a variety of names, such as protocol data packets, frames, segments, cells, etc., depending on the specific context, the specific protocol used, and certain other conventions. In the context of the present document, all such packets of data shall generically be referred to as data packets. The procedures for placing data packets into a queue, advancing them in the queue, and removing data packets from the queue are referred to as “queue management”.
A phenomenon that is known in data packet transmission networks is that of congestion. Congestion implies a state in which it is not possible to readily handle the number of data packets that are required to be transported over that connection or link. As a consequence of congestion at a given link, the number of data packets in a queue buffer associated with said link will increase. In response to a congestion condition, it is known to implement a data packet dropping mechanism referred to as “drop-on-full”. According to this mechanism, upon receipt of a new data packet at the queue buffer, a queue length related parameter, such as the actual queue length or the average queue length, is compared to a predetermined threshold. If the predetermined threshold is exceeded, then a data packet is dropped. The threshold indicates the “full” state of the queue.
The data packet which is dropped can be the newly arrived packet, in which case the mechanism is called “tail-drop”. Besides the technique of tail-drop, it is also known to perform a so-called “random-drop”, where a data packet already in the queue is selected according to a random function, or a so-called “front-drop”, where the first data packet in the queue is dropped. Such drop-on-full mechanisms not only serve to reduce the load on the congested link, but also serve as an implicit congestion notification to the source and/or destination of the data packet.
The so-called “Transmission Control Protocol” (TCP) is a commonly used protocol for controlling the transmission of data packets (or “packets”) over an IP network. When a TCP connection between peer hosts is initiated, TCP starts transmitting data packets at a relatively low rate. The transmission rate is slowly increased in order to avoid causing an overflow at routers of the IP network (which would result in the loss of data packets and the need to resend these lost packets). The rate at which data packets can be transmitted is defined by two variables, cwnd and ssthresh. TCP uses acknowledgement messages to control the transmission rate, and is constantly probing the link for more transmission capacity.
The variable cwnd defines the number of unacknowledged data packets which the TCP sender may have in “flight” at any given time. At the beginning of a communication, cwnd is set at a low value (e.g. one segment) and the system is in a “slow start” mode. Following receipt of the first acknowledgement from the receiver, cwnd is increased in size by one packet (to two packets). Two further packets are then sent. When an acknowledgement is received by the sender for each further packet, cwnd is increased by one packet. Once both packets have been acknowledged, the size of cwnd is four packets. This process is repeated resulting in an exponential opening of the congestion window. The variable ssthresh is initially set to some fixed level (e.g. 65535 bytes), and the slow start mode continues until cwnd>ssthresh. Thereafter, a “congestion avoidance” mode is entered during which cwnd is increased by just 1/cwnd each time a successful transmission acknowledgement is received. The variable cwnd has an upper limit defined either by the sender or by an advertisement message sent from the receiver.
If congestion occurs as indicated by a timeout (of a controlling timer at the sender), ssthresh is set to one half of the previous value of cwnd, and cwnd is set to 1. Thus, the slow start mode is re-entered and continued until such time as the transmission rate (defined by cwnd) reaches half the rate which last caused congestion to occur. Thereafter, the congestion avoidance mode is entered. If congestion is indicated by receipt of a third duplicate acknowledgements by the sender (indicating that a given data packet has not been received by the receiver despite the receipt of three subsequent segments), ssthresh is set to one half of the previous value of cwnd whilst shrinks to ssthresh. Receipt of three duplicate acknowledgements causes the TCP sender to retransmit the missing data packet using the “fast retransmit” mechanism. After retransmitting the missing data packet, fast recovery takes over. The value of cwnd is set to ssthresh+3, and is increased by 1 packet for each additional duplicate acknowledgement received. An acknowledgement which acknowledges the retransmitted data packet sets cwnd to ssthresh, putting the sender back into congestion avoidance mode.
In any IP packet transmission path, bottlenecks will occur which limit the transmission rate of the available transmission route (or link). In conventional networks, bottlenecks may occur for example at IP routers. Routers handle bottlenecks by using buffers to queue incoming data. If the tail dropping mechanism described above is used to deal with congestion, there is a high probability that two or more packets from the same connection will be dropped. The loss of two or more packets from the same sending window of a TCP connection may cause the TCP sender to enter the slow start mode. This timer-triggered loss recovery may lead to under-utilisation of the link, in particular when the link incorporates significant delays. This in turn results in a waste of link resources and perceived poor link performance on the part of the user.
The tail dropping mechanism may also cause problems due to “global synchronisation”. This phenomenon arises when several TCP connections simultaneously reduce their load. The queue serving the connections may be drained resulting in large fluctuations in the buffer level.
In order to avoid the adverse effects of tail dropping, methods to detect congestion before the absolute limit of the queue is reached have been developed. In general these Early Congestion Detection methods make use of one or more queue threshold levels to determine whether or not a packet arriving at a queue should be accepted or dropped. In the so-called “Random Early Detection” method, RED, [IETF RFC2309], a minimum threshold level Tmin and a maximum threshold level Tmax are defined. If the queue size remains below the minimum threshold level, all packets arriving at the queue are accepted and placed at the back of the queue. If the queue size exceeds the maximum threshold level, all packets arriving at the queue are dropped. If the queue size is between the maximum and minimum thresholds, packets are dropped with a certain probability. However, this tends to result in only a fraction of the large set of TCP connections (that share the congested router) reducing their load simultaneously. For a queue fill level greater than the maximum threshold, RED works according to the conventional tail drop scheme. The key to the RED algorithm lies in the early congestion notifications that are transmitted to randomly chosen TCP users by dropping a few packets probabilistically when the queue level exceeds the minimum threshold. Since the congestion feedback is transmitted to a limited number of link users, global synchronisation can be avoided.
In order to allow for a certain level of short-term fluctuations in the queue caused by packet bursts (a property inherent to IP transmissions), the RED algorithm does not operate on the instantaneous queue level, but rather on a moving average measure of the queue level qavg(.). When using the RED algorithm, there are four parameters that have to be set by the operator; a queue filter constant wq, the two queue thresholds Tmin and Tmax, and the parameter pmax which defines the maximum probability for a packet discard when Tmin<qavg(.)<Tmax.
RED is reported to work well with high capacity routers. A large number of TCP connections are required to overload such capacity. RED relies heavily on this fact: at congestion there are a large number of connections sharing the queue. It thus makes sense to “signal” congestion to only a small fraction of users at the same time in order to avoid global synchronisation.
In the paper “Random Early Detection Gateways for Congestion Avoidance” by Sally Floyd and Van Jacobson, IEEE/ACM Transactions on networking, August 1993, an extensive discussion of the RED algorithm is given, where the minimum threshold minth, maximum threshold maxth, and the maximum probability maxp are all set as fixed parameters. Regarding the choice of minth and maxth, it is mentioned that the optimum values for these thresholds depend on the desired average queue size, and the optimal value for maxth depends in part on the maximum average delay over the link. Furthermore, it is stated that maxth should at least be twice as large as minth.
In an internet document discussing the setting of RED parameters, published by Sally Floyd at http://www.acir.org/floyd/REDparameter.txt, it is mentioned that the optimum value for fixing minth will depend partly on the link speed, the propagation delay and the maximum buffer size.
In the article “Techniques for eliminating packet loss in congested TCP-IP networks” by Wu-chang Feng et al., November 1997, a so-called adaptive RED is proposed, in which the probability parameter maxp is adapted to the traffic load. Although the detailed algorithm described in this document uses fixed thresholds, it is indicated that the threshold values could also be made dependent on the input traffic. A similar proposal is made in the article “A self configuring RED gateway” by Wu-Chang Feng et al., Infocom '99, March 1999.
Another proposal for improving RED is made in WO 00/60817, in which a differentiation is introduced between traffic originating from rate adaptive applications that respond to packet loss. This document suggests introducing at least two drop precedent levels, referred to as “in profile” and “out profile”. Each drop precedent level has its own minimum threshold minth and/or maximum threshold maxth.
From WO 00/57599 a queue management mechanism is known in which drop functions are selected according to ingress flow rate measurements and flow profiles.
From U.S. Pat. No. 6,134,239 a method of rejecting ATM cells at an overloaded load buffer is known. The concept of RED is mentioned. According to this document, a first threshold related to the overloaded buffer queue, and a second threshold associated with a specific connection are monitored, and incoming packets are dropped for the specific connection if both thresholds are exceeded.
U.S. Pat. No. 5,546,389 describes a method for controlling access to a buffer and is specifically concerned with ATM buffers. The use of one or more thresholds and the dynamic control of such thresholds is mentioned, where the dynamics are determined on the basis of incoming and outgoing traffic.
EP-1 028 600 describes a buffer management scheme with dynamic queue length thresholds for ATM switches. A common threshold is dynamically updated every time a new cell arrives, where the new value is determined based on traffic condition.
Another improvement proposal for RED is described in EP-0 872 988, which has the object of providing isolation when connections using different TCP versions share a bottleneck link. The solution proposed in this document is the use of bandwidth reservation guarantees for each connection. If one connection is being under-utilised, then another connection may use a part of the under-utilised connection's bandwidth. When the connection needs to reclaim its buffer space a predetermined package dropping mechanism is operated, such as a longest queue first (LQF) mechanism.
It will be appreciated that mechanisms such as RED may be employed to trigger the “marking” of data packets when a buffer queue starts to be full. Thus, rather than dropping a packet, the mechanism may add a tag to a packet forwarded to a receiver to notify the receiver that action should be taken to avoid congestion. The receiver may in turn notify the sender. Alternatively, a marked data packet or other notification may be returned directly to the sender.
Whilst much of the state of the art in this area is concerned with IP network routers and the like, the problems of congestion and buffer queue management also arise in mobile communication systems such as cellular telephone networks.
It will be appreciated that queue management of buffers is required when handling packet data traffic which is time critical, such as streaming media content. It may not be possible to tolerate excessive delays in the delivery of such traffic (streaming data may be sent over a UDP connection rather than a TCP connection). Some of the principles and solutions discussed above and below may be applicable to this situation.